#include<iostream>
#include<cstdio>
#include<ctime>
#include<algorithm>
#include<cstdlib>
using namespace std;

int getMax(int* p,int len)
{
    int m=p[0];
    for(int i=1;i<len;++i)
    {if(p[i]>m){m=p[i];}}
    return m;
}

void count_sort(int* p,int len,int cot)
{
    int temp[len];//不报错？？？
    int buckets[10]={0};
    for(int i=0;i<len;++i)
    {buckets[(p[i]/cot)%10]++;}
    for(int i=1;i<10;++i)
    {buckets[i]+=buckets[i-1];}
    for(int i=len-1;i>=0;--i)
    {
        temp[buckets[(p[i]/cot)%10]-1]=p[i];
        buckets[(p[i]/cot)%10]--;
    }
    for(int i=0;i<len;++i)
    {p[i]=temp[i];}
}


int main()
{
    srand((unsigned)time(NULL));
    clock_t start,end;
    int arr[100];
    int len=100;
    for(int i=0;i<len;++i)
    {arr[i]=rand()%len;}

    start=clock();

    //count_sort
    int maxA=getMax(arr,len);
    for(int cot=1;maxA/cot>0;cot*=10)
    {count_sort(arr,len,cot);}

    //sort(arr,arr+len);

    end=clock();
    printf("\ntime=%.6lf\n",(double)(end-start));//CLOCKS_PER_SEC
    // for(int i=0;i<len;++i)
    // {printf("%d ",arr[i]);}

    return 0;
}

